//
//  LinkedList_uniquify.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/8.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension LinkedList where Element: Comparable {
    
    /// 有序向量去重
    public func uniquify() -> Int {
        if _size < 2 { return 0 }
        let oldSize = _size
        _size = 1
        var end = first
        var nd = first?.successor
        while let node = nd, node !== _trailer {
            if end != nd {
                _size += 1
                end = end?.successor
                end?.value = nd?.value
            }
            nd = node.successor
        }
        
        // 删除重复元素
        end?.successor = _trailer
        _trailer.predecessor = end
        
        return oldSize - _size
    }
}
